﻿using System;
using System.Linq;
using Algoritmia.DataStructures.Lists;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Utils;

namespace Algoritmia.Problems.GeneralizedCoinChange.QuantityAndSizeModeling
{
    public class SpaceSavingDynamicCoinChanger2 : IDynamicCoinChanger
    {
        private readonly IList<int> _values;
        private readonly int _n;
        private readonly IList<double> _weights;
        private readonly Func<IMap<Tuple<int, int>, double>> _createMap;

        public SpaceSavingDynamicCoinChanger2(IList<int> values, IList<double> weights = null,
             Func<IMap<Tuple<int,int>,double>> createMap = null)
        {
            _createMap = createMap ?? (() => AlgoritmiaFactory.Maps<Tuple<int, int>, double>.Default);
            _values = values;
            _n = values.Count;
            _weights = weights ?? Enumerable.Repeat(1.0,_n).ToAlgoritmiaList();
        }

        #region Implementation of IDynamicCoinChanger

        public double Weight(int Q)
        {
            var mem = _createMap();
            mem[new Tuple<int, int>(0, 0)] = 0;
            for(int q = 1; q <= Q; q++)
            {
                mem[new Tuple<int, int>(q, 0)] = double.PositiveInfinity;
            }

            for(int n = 1; n <= _n; n++)
            {
                for(int q = 0; q <= Q; q++)
                {
                    mem[new Tuple<int, int>(q, n % 2)] = Enumerable.Range(0, (q / _values[n - 1]) + 1).Select(
                            i => mem[new Tuple<int, int>(q - i * _values[n - 1], (n - 1)%2)] + i * _weights[n - 1]).Min();
                }
            }

            return mem[new Tuple<int, int>(Q, _n%2)];
        }

        #endregion
    }
}
